package com.pp.arithmeticcommon.utils.sort;

import lombok.*;

import java.util.*;

/**
 * Dijkatra最短路径算法
 */
@NoArgsConstructor(access = AccessLevel.PRIVATE)
public class DijkstraAlgorithm {

    /**
     * 距离表
     */
    @Getter
    private static int[] distances;

    /**
     * 前置顶点表
     */
    @Getter
    private static int[] prevs;

    @Getter
    private static List<String> path = new ArrayList<String>();

    /**
     * Dijkatra最短路径算法获取指定顶点开始的最短距离表
     *
     * @param graph      图
     * @param startIndex
     * @return
     */
    public static void dijkstra(Graph graph, int startIndex) {
        //图的顶点数量
        int size = graph.vertexes.length;
        //创建距离表，存储从起点到每一个顶点的临时距离
        distances = new int[size];
        //创建前置顶点表，存储从起点到每一个顶点的已知最短路径的前置节点
        prevs = new int[size];
        //记录顶点遍历状态
        boolean[] access = new boolean[size];

        //初始化最短路径表，到达每个顶点的路径代价默认为无穷大
        for (int i = 1; i < size; i++) {
            distances[i] = Integer.MAX_VALUE;
        }
        //遍历起点，刷新距离表
        access[0] = true;
        List<Edge> edgesFromStart = graph.adj[startIndex];
        for (Edge edge : edgesFromStart) {
            distances[edge.index] = edge.weight;
            prevs[edge.index] = 0;
        }
        //主循环，重复 遍历最短距离顶点和刷新距离表 的操作
        for (int i = 1; i < size; i++) {
            //寻找最短距离顶点
            int minDistanceFromStart = Integer.MAX_VALUE;
            int minDistanceIndex = -1;
            for (int j = 1; j < size; j++) {
                if (!access[j] && distances[j] < minDistanceFromStart) {
                    minDistanceFromStart = distances[j];
                    minDistanceIndex = j;
                }
            }
            if (minDistanceIndex == -1) {
                break;
            }
            //遍历顶点，刷新距离表
            access[minDistanceIndex] = true;
            for (Edge edge : graph.adj[minDistanceIndex]) {
                if (access[edge.index]) {
                    continue;
                }
                int weight = edge.weight;
                int preDistance = distances[edge.index];
                if (weight != Integer.MAX_VALUE && (minDistanceFromStart + weight < preDistance)) {
                    distances[edge.index] = minDistanceFromStart + weight;
                    prevs[edge.index] = minDistanceIndex;
                }
            }
        }

        //遍历获取最短路径
        createPrevs(graph.getVertexes(), prevs, graph.getVertexes().length - 1);
    }

    public static void createPrevs(Vertex[] vertices, int[] prev, int i) {
        if (i > 0) {
            createPrevs(vertices, prev, prev[i]);
        }
        path.add(vertices[i].data);
//        System.out.println(vertices[i].data);
    }

    /**
     * 图的顶点
     */
    @AllArgsConstructor
    public static class Vertex {
        String data;
    }

    /**
     * 图的边
     */
    @AllArgsConstructor
    public static class Edge {
        int index;
        int weight;
    }

    /**
     * 图
     */
    @Getter
    @Setter
    public static class Graph {
        private Vertex[] vertexes;
        private LinkedList<Edge> adj[];

        public Graph(int size) {
            //初始化顶点和邻接矩阵
            vertexes = new Vertex[size];
            adj = new LinkedList[size];
            for (int i = 0; i < adj.length; i++) {
                adj[i] = new LinkedList<Edge>();
            }
        }
    }

}

